package leetcode.editor.offer;

import com.sun.org.apache.bcel.internal.generic.ARETURN;

import java.util.*;

// 37. 序列化二叉树
// https://leetcode.cn/problems/xu-lie-hua-er-cha-shu-lcof/
class XuLieHuaErChaShuLcof {
    public static void main(String[] args) {
//        Solution solution = new XuLieHuaErChaShuLcof().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    public class Codec {

        // Encodes a tree to a single string.
        /*public String serialize(TreeNode root) {
            if (root == null) {
                return "[]";
            }
            Queue<TreeNode> queue = new LinkedList<>();
            queue.offer(root);
            StringBuffer sb = new StringBuffer();
            sb.append("[");
            while (!queue.isEmpty()) {
                int len = queue.size();
                while (len > 0) {
                    TreeNode node = queue.poll();
                    if (node != null) {
                        sb.append(node.val + ",");
                        queue.offer(node.left);
                        queue.offer(node.right);
                    } else {
                        sb.append("null,");
                    }
                    len--;
                }
            }
            sb.deleteCharAt(sb.length() - 1);
            sb.append("]");

            return sb.toString();
        }

        // Decodes your encoded data to tree.
        public TreeNode deserialize(String data) {
            if (data.equals("[]")) {
                return null;
            }

            // 除去左右括号和分割逗号
            String[] vals = data.substring(1, data.length() - 1).split(",");
            TreeNode root = new TreeNode(Integer.parseInt(vals[0]));
            Queue<TreeNode> queue = new LinkedList<>();
            queue.add(root);
            int index = 1;

            while (!queue.isEmpty()) {
                TreeNode node = queue.poll();
                if (!vals[index].equals("null")) {
                    node.left = new TreeNode(Integer.parseInt(vals[index]));
                    queue.offer(node.left);
                }
                // 跳到下一个
                index++;

                if (!vals[index].equals("null")) {
                    node.right = new TreeNode(Integer.parseInt(vals[index]));
                    queue.offer(node.right);
                }
                // 跳到下一个
                index++;
            }
            return root;
        }*/

        // dfs
        /*public String serialize(TreeNode root) {
            StringBuilder sb = new StringBuilder();
            sb.append("[");
            rserialize(root, sb);
            sb.append("]");
            return sb.toString();
        }

        public StringBuilder rserialize(TreeNode root, StringBuilder sb) {
            if (root == null) {
                sb.append("null,");
                return null;
            }

            sb.append(root.val + ",");
            rserialize(root.left, sb);
            rserialize(root.right, sb);
            return sb;
        }

        // Decodes your encoded data to tree.
        public TreeNode deserialize(String data) {
            List<String> dataList = new ArrayList<>(Arrays.asList(data.substring(1, data.length() - 1).split(",")));
            return rdeserialize(dataList);
        }

        public TreeNode rdeserialize(List<String> dataList) {
            // 如果第一个等于null，那么不再递归赋值
            if (dataList.get(0).equals("null")) {
                // 移除该值
                dataList.remove(0);
                return null;
            }

            // 此时赋值给一个新节点
            TreeNode node = new TreeNode(Integer.parseInt(dataList.get(0)));
            // 移除该值
            dataList.remove(0);
            node.left = rdeserialize(dataList);
            node.right = rdeserialize(dataList);
            return node;
        }*/

        // Encodes a tree to a single string.
        public String serialize(TreeNode root) {
            if (root == null) {
                return "[]";
            }

            StringBuilder sb = new StringBuilder();
            Queue<TreeNode> queue = new LinkedList<>();
            queue.offer(root);
            while (!queue.isEmpty()) {
                int size = queue.size();
                for (int i = 0; i < size; i++) {
                    TreeNode node = queue.poll();

                    if (node != null) {
                        sb.append(node.val + ",");
                        queue.offer(node.left);
                        queue.offer(node.right);
                    } else sb.append("null,");
                }
            }

            return sb.deleteCharAt(sb.length() - 1).toString();
        }

        // Decodes your encoded data to tree.
        public TreeNode deserialize(String data) {
            if (data.equals("[]")) return null;
            String[] vals = data.split(",");
            Queue<TreeNode> queue = new LinkedList<>();
            TreeNode root = new TreeNode(Integer.parseInt(vals[0]));
            queue.offer(root);
            int idx = 1;
            while (!queue.isEmpty()) {
                TreeNode node = queue.poll();

                if (!vals[idx].equals("null")) {
                    node.left = new TreeNode(Integer.parseInt(vals[idx]));
                    queue.offer(node.left);
                }
                idx++;

                if (!vals[idx].equals("null")) {
                    node.right = new TreeNode(Integer.parseInt(vals[idx]));
                    queue.offer(node.right);
                }
                idx++;
            }
            return root;
        }

    }

// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));
//leetcode submit region end(Prohibit modification and deletion)

}
